package 代码随想录_回溯.组合;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

/**
 * @author zx
 * @create 2022-06-09 11:32
 */
public class 组合总和II_40 {
    /**
     * 去除树层的重复元素,还是这种好理解,used数组那个不好
     */
    List<List<Integer>> res = new ArrayList<>();
    LinkedList<Integer> list = new LinkedList<>();
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        Arrays.sort(candidates);//需要排序//只有当给定集合中有重复数字且结果集不要重复时,才这样：同47
        dfs(candidates,target,0,0);
        return res;
    }
    private void dfs(int[] candidates,int target,int sum,int startIndex){
        if(sum > target){
            return;
        }
        if(sum == target){
            res.add(new ArrayList<>(list));
            return;
        }
        for(int i = startIndex;i < candidates.length;i++){
            // 要对同一树层使用过的元素进行跳过(结果集去重)
            if (i > startIndex && candidates[i] == candidates[i - 1]) {
                continue;
            }
            sum += candidates[i];
            list.add(candidates[i]);
            dfs(candidates,target,sum,i + 1);//i+1,每个数字在每个组合中只能使用一次
            sum -= candidates[i];
            list.removeLast();
        }
    }
}
